package 图.树;
/**
 * 树形dp  
 * 左子树 要信息 
 * 右子树 要信息 
 * 整合 当前节点的 信息 返回 上一层
 * 
 * 最重要的 是 infor 信息 需要 包括 那些 内容 
 * 这一 节 内容 再去 看一 下 左程云的 总结
 *
 */
public class leetcode2265树形dp {
	public static void main(String []args) {
		TreeNode root = new TreeNode(4,new TreeNode(8,null,null),new TreeNode(5,null,null));
		System.out.println(solution(root));
	}
	static class Infor{
		/**
		 * sum : 是 当前节点 包括  子节点的 总和
		 * num ： 包括 当前 节点在内的 节点的数量
		 * ans ： 符合要求的 答案 
		 */
		int sum;
		int num;
		int ans;
		public Infor(int sum,int num,int ans) {
			this.ans = ans;
			this.sum = sum;
			this.num = num;
		}
		public String toString() {
			return sum + "  " + num + " " + ans; 
		}
	}
	/**
	 * 针对该题 采用 后序遍历的策略
	 * 不能 说采用 后续遍历的策略 吧只能 说 最终整合信息的 返回 是  在 最后
	 */
	static Infor solution(TreeNode root) {
		if(root == null)
			return new Infor(0,0,0);
		Infor leftData = solution(root.left);
		Infor rightData = solution(root.right);
		int sum = leftData.sum  + rightData.sum + root.val;
		int num = leftData.num + rightData.num + 1;
		/**
		 * 错误 代码   优先级的 问题 我靠  （敲）
		 * 
		 * 逻辑运算符的 优先级 小于 算数运算符
		 * int ans = leftData.ans + rightData.ans + sum / num == root.val ? 1 : 0;
		 * 
		 * 正确代码
		 * int ans = leftData.ans + rightData.ans + (sum / num == root.val ? 1 : 0);
		 * 
		 */
		int ans = leftData.ans + rightData.ans + (sum / num == root.val ? 1 : 0);
		return new Infor(sum,num,ans);
	}




	public int solve(TreeNode root){
		return recursion(root)[2];
	}

	// int [] {} , [0] 表示当前节点的 sum , [1] 表示以当前节点为头节点的 节点个数,  [2] 以当前 node节点 为 头节点 表示 满足 要求的 答案数
	public int[] recursion(TreeNode node){
		if(node == null){
			return new int[]{0,0,0};
		}
		int left[] = recursion(node.left);
		int right[] = recursion(node.right);
		int curSum = left[0] + right[0] + node.val;
		int curNode = left[1] + right[1] + 1;
		int curAns = left[2] + right[2];
		if(curSum / curNode == node.val){
			curAns++;
		}
		return new int[]{curSum,curNode,curAns};
	}

	
}
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }